package LeetCode.interview;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;

import LeetCode.interview._104_Maximum_Depth_of_Binary_Tree.TreeNode;

import sun.tools.jar.resources.jar;
import util.LogUtils;

/*
 * 
原题　
		 You are given an n x n 2D matrix representing an image.
	
	Rotate the image by 90 degrees (clockwise).
	
	Follow up:
	Could you do this in-place?
	
		Given input matrix = 
	[
	  [1,2,3],
	  [4,5,6],
	  [7,8,9]
	],
	
	rotate the input matrix in-place such that it becomes:
	[
	  [7,4,1],
	  [8,5,2],
	  [9,6,3]
	]
	
	Example 2:
	
	Given input matrix =
	[
	  [ 5, 1, 9,11],
	  [ 2, 4, 8,10],
	  [13, 3, 6, 7],
	  [15,14,12,16]
	], 
	
	rotate the input matrix in-place such that it becomes:
	[
	  [15,13, 2, 5],
	  [14, 3, 4, 1],
	  [12, 6, 8, 9],
	  [16, 7,10,11],
	]


题目大意
	　
	给定一个n*n个2维矩阵来表示一个图。在原矩阵上旋转图形90°。
解题思路
	
 * @Date 2017-10-07 01：15
 */
public class _048_Rotate_Image {
	/**
	 * 法一：
	 * 	new出一个一模一样的矩阵, so easy~~
		空间复杂度较高，开辟额外的空间开复制原矩阵。但是最好理解
		找到规律即可：matrix[j][l-i-1]=temmatrix[i][j];
		temmatrix 这里储存的是原矩阵
	 * @param matrix
	 */
    public void rotate(int[][] matrix) {
        int h = matrix.length;  
        int l = matrix[0].length;  
        int tem[][] = new int[h][l];
        //复制
        for(int i=0;i<h;i++)  
            for(int j=0;j<l;j++)  
                tem[i][j]=matrix[i][j];  
        //旋转
        for(int i=0;i<h;i++)  
            for(int j=0;j<l;j++)  
                matrix[j][l-i-1]=tem[i][j];            
    }  
    
    /**
     * 基本思路是把图片分为行数/2层，然后一层层进行旋转，每一层有上下左右四个列，然后目标就是把上列放到右列，右列放到下列，下列放到左列，左列放回上列，中间保存一个临时变量即可。
     * 即：从外层向内侧一圈圈的转
     * 		。。。。。画画图自己理解下吧
     * @param matrix
     */
    public void rotate2(int[][] matrix) {
    	int n = matrix.length;
	    for (int i = 0; i < n / 2; i++) {
	        for (int j = 0; j < Math.ceil(((double) n) / 2.); j++) {
	            int temp = matrix[i][j];
	            matrix[i][j] = matrix[n-1-j][i];
	            matrix[n-1-j][i] = matrix[n-1-i][n-1-j];
	            matrix[n-1-i][n-1-j] = matrix[j][n-1-i];
	            matrix[j][n-1-i] = temp;
	        }
	    }
    }
    
	public static void main(String[] args) {
		_048_Rotate_Image obj = new _048_Rotate_Image();


		obj.rotate(new int[][] 	
				{
		                   	  {1, 2, 3},
		                	  {4, 5, 6},
		                	  {7, 8, 9}
				}
		);
	}

}
